// https://leetcode.cn/problems/ransom-note/
// Created by ade on 2022/8/4.
//
#include<iostream>
#include<string>
#include<algorithm>
#include<unordered_map>

using namespace std;

class Solution {
public:
    // 给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
    // magazine是否包含ransomNote
    bool canConstruct(string ransomNote, string magazine) {
//        sort(ransomNote.begin(), ransomNote.end());
//        sort(magazine.begin(), magazine.end());
//        if (ransomNote == magazine)
//            return true;
//        int iLen = ransomNote.size(); // aa
//        int jLen = magazine.size();// aab
//        if (iLen > jLen || iLen == jLen && ransomNote != magazine) return false;
        int iLen = ransomNote.size(); // aa
        int jLen = magazine.size();// aab
        int i = 0, j = 0;
        for (; i < iLen; i++) {
            if (ransomNote[i] == magazine[j]) {
                cout << "match i:" << i << "-" << ransomNote[i] << endl;
                j++;
                continue;
            }
            while (j < jLen) {
                j++;
                if (ransomNote[i] == magazine[j]) {
                    cout << "match i:" << i << "---" << ransomNote[i] << endl;
                    j++;
                    break;
                }
            }

            if (j == jLen) {
                if (ransomNote[i] == magazine[j - 1]){
                    cout << "i:" << i << endl;
                    break;
                }

                else
                    return false;
            }
        }
        cout << "i:" << i << endl;
//        cout << "j:" << j << endl;
        return i == iLen;
    }

    bool canConstruct1(string ransomNote, string magazine) {
        int r[26] = {0};
        for (auto i : magazine) {
            r[i - 'a']++;
        }
        for (auto i : ransomNote) {
            r[i - 'a']--;
            if (r[i - 'a'] < 0) return false;
        }
        return true;
    }
};

int main() {
    Solution so;
    string ransomNote = "aa";
    string magazine = "aab";
    if (so.canConstruct(ransomNote, magazine)) cout << "yes" << endl;
    else cout << "no";
    return 0;
}